// 1 2 3 5 8
#include <stdio.h>
#include <iostream>

using namespace std;
int main()
{
    int fib[10001] = {0, 1, 2};
    for(int i = 3; i < 10001; ++i){
        fib[i] = fib[i-1] + fib[i-2];
        fib[i] %= 10000;   // 四位密码
    }
    int n;
    while(cin >> n){
        for(int i = 0; i < n; ++i){
            int num;
            cin >> num;
            printf("%04d", fib[num]);  // 格式化输出，不够四位补零
        }
        printf("\n");
    }
    return 0;
}